package com.it.data_linkedList.leetcode;

import com.it.data_tree.util.ColorPrintln;

/**
 * @author: Coke
 * @DateTime: 2023/06/08/21:54
 * 判断是否为回文链表
 **/
public class E07LeetCode234 {
    /*
     * 1. 找中间节点
     * 2. 中间节点后半个链表反转
     * 3. 反转后链表与原链表一一比较
     * */
    
    /**
     * 找中间节点
     *
     * @return ListNode
     * @DateTime: 2023/6/8 21:57
     * @author: Coke
     */
    public static ListNode middle (ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode n1 = node;
        ListNode n2 = node;
        while (n2 != null && n2.next != null) {
            n1 = n1.next;
            n2 = n2.next.next;
        }
        return n1;
    }
    
    /**
     * 反转链表
     *
     * @param node:
     * @return ListNode
     * @DateTime: 2023/6/8 22:03
     * @author: Coke
     */
    public static ListNode reverse (ListNode node) {
        ListNode n1 = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = n1;
            n1 = node;
            node = next;
        }
        return n1;
    }
    
    /**
     * 执行逻辑
     *
     * @param node:
     * @return Boolean
     * @DateTime: 2023/6/8 22:16
     * @author: Coke
     */
    public static Boolean isPalindrome (ListNode node) {
        ColorPrintln.pinkPrintln("原链表：" + node);
        // 1. 找出中间节点
        ListNode middle = middle(node);
        ColorPrintln.bluePrintln("中间节点：" + middle);
        // 2. 反转链表
        ListNode reverse = reverse(middle);
        ColorPrintln.greenPrintln("反转后：" + reverse);
        // 3. 一一对比
        while (reverse != null) {
            if (reverse.val == node.val) {
                reverse = reverse.next;
                node = node.next;
            } else {
                return false;
            }
        }
        return true;
    }
    
}
